//
// Created by Administrator on 2021/4/13.
//

/*
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

 

示例 1：

输入：
3
/ \
  9  20
/  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 层序遍历
vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> ret;
    if (!root) {
        return ret;
    }
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = (int) q.size();
        ret.emplace_back();
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front();
            q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return ret;
}

class Solution {
public:
    vector<double> averageOfLevels(TreeNode *root) {
        vector<double> ret;
        if (!root) return ret;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int currentNum = (int) q.size();
            double valSum = 0;
//            double sum = accumulate(q.) 队列没法获得begin end  迭代器
            for (int i = 1; i <= currentNum; ++i) {
                auto node = q.front();
                q.pop();
                valSum += node->val;  // 累加
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ret.push_back(valSum / currentNum);
        }
        return ret;
    }
};
class Solution2 {  // 题解 dfs  得记录每个节点的层级
public:
    vector<double> averageOfLevels(TreeNode* root) {
        auto counts = vector<int>();
        auto sums = vector<double>();
        dfs(root, 0, counts, sums);
        auto averages = vector<double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.push_back(sums[i] / counts[i]);
        }
        return averages;
    }

    void dfs(TreeNode* root, int level, vector<int> &counts, vector<double> &sums) {
        if (root == nullptr) {
            return;
        }
        if (level < sums.size()) {
            sums[level] += root->val;
            counts[level] += 1;
        } else {
            sums.push_back(1.0 * root->val);
            counts.push_back(1);
        }
        dfs(root->left, level + 1, counts, sums);
        dfs(root->right, level + 1, counts, sums);
    }
};


int main() {
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);
    Solution sol;
    vector<double> ans = sol.averageOfLevels(&t1);
    for (auto &x:ans) cout << x << endl;
    return 0;
}